/// [Factorial digit sum](https://projecteuler.net/problem=20)
fn main() {
    for n in &[10, 100] {
        println!(
            "The sum of the digits in the number {}! is {}",
            n,
            factorial_digit_sum(n)
        );
    }
}
fn factorial_digit_sum(num: &u8) -> u128 {
    let num = *num as u128;
    let max = 10_u128.pow(30);
    let mut mul = vec![1];
    for mut i in 2..=num {
        if i % 10 == 0 {
            i /= 10;
        }
        for item in mul.iter_mut() {
            *item *= i;
        }
        for j in 0..(mul.len() - 1) {
            if mul[j] > max {
                mul[j + 1] += mul[j] / max;
                mul[j] %= max;
            }
        }
        let j = mul.len() - 1;
        if mul[j] > max {
            mul.push(mul[j] / max);
            mul[j] %= max;
        }
    }
    let mut sum = 0;
    for mut item in mul {
        while item > 10 {
            sum += item % 10;
            item /= 10;
        }
        sum += item;
    }
    sum
}
